CS 5010: Problem Set 7

Out: Monday, October 26, 2015

Due: Monday, November 2, 2015 at 600pm local time.

The goal of this problem set is to give you practice using context arguments and invariants.

Remember that you must follow the design recipe, and write invariants (as WHERE clauses) whenever an argument represents context information.

You must use DrScheme's HtDP Intermediate Student Language with Lambda. Use list abstractions like filter, fold, and map whenever they are helpful. As before, you will be penalized for failing to use these when they are "obviously" applicable.

Note: not everything on this problem set requires the use of invariants; some may only require generalization. Part of your task is to figure out when you need an invariant and when you do not. Remember, it is the purpose statement that determines whether or not you need to state an invariant.

Remember that you must follow the design recipe. Your deliverables include the data definitions (including interpretation and templates), contract and purpose header, strategies, code, and tests. Be sure to sync your work and fill out a Work Session Report at the end of every work session. Use the Work Session Report for PS07.

As usual, the rubric for grading is here.

The first few problems on this problem set have to do with outlines. Consider a text in the form of an outline, for example:

1 The first section
1.1 A subsection with no subsections
1.2 Another subsection
1.2.1 This is a subsection of 1.2
1.2.2 This is another subsection of 1.2
1.3 The last subsection of 1
2 Another section
2.1 More stuff
2.2 Still more stuff

The point of an outline is to impose a tree structure on a document, so it is natural to represent an outline as a tree. For example, the outline above might be represented as:

  (list 
    (make-section "The first section"
      (list
        (make-section "A subsection with no subsections" empty)
        (make-section "Another subsection"
          (list
            (make-section "This is a subsection of 1.2" empty)
            (make-section "This is another subsection of 1.2" empty)))
        (make-section "The last subsection of 1" empty)))
    (make-section "Another section"
      (list
        (make-section "More stuff" empty)
        (make-section "Still more stuff" empty))))

using the data definition

;; An Outline is a ListOfSection
;; A Section is a (make-section String ListOfSection)
;; INTERP: (make-section str secs) is a section where
;; str is the header text of the section
;; secs is the list of subsections of the section

We'll call this the tree representation

Another representation of an outline could be as a list with one element per section or subsection. Each element of the list would consist of two members: the section number, represented as a list of natural numbers, and a string. This would look more like the text representation. We call this the flat representation.

In the flat representation, the outline above would be represented as

  (list
    (make-line (list 1) "The first section")
    (make-line (list 1 1) "A subsection with no subsections")
    (make-line (list 1 2) "Another subsection")
    (make-line (list 1 2 1) "This is a subsection of 1.2")
    (make-line (list 1 2 2) "This is another subsection of 1.2")
    (make-line (list 1 3) "The last subsection of 1")
    (make-line (list 2) "Another section")
    (make-line (list 2 1) "More stuff")
    (make-line (list 2 2) "Still more stuff"))